//198:打家劫舍1 https://leetcode-cn.com/problems/house-robber/
class Solution {
public:
    int rob(vector<int>& nums) {
        if(nums.size() == 1)
        {
            return nums[0];
        }
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i-2] + nums[i] , dp[i - 1]);
        }
        return dp[nums.size()-1];
    }
};


//213.打家劫舍2 https://leetcode-cn.com/problems/house-robber-ii/submissions/
class Solution {
public:
    int money(vector<int>& nums)
    {
         if(nums.size() == 1)
            return nums[0];
        if(nums.size() == 0)
            return 0;
        vector<int> dp(nums.size());
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2; i < nums.size(); i++)
        {
            dp[i] = max(dp[i-2] + nums[i] , dp[i - 1]);
        }
        return dp[nums.size()-1];
    }
    int rob(vector<int>& nums) {
        if(nums.size() == 1)
            return nums[0];
        if(nums.size() == 0)
            return 0;
        vector<int> nums1(nums.begin() + 1,nums.end());
        vector<int> nums2(nums.begin(),nums.end()-1);
        int res1 = money(nums1);
        int res2 = money(nums2);
        return max(res1,res2);
    }
};